package leetcode;

import util.ListNode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0092.java
 * @Author : WangRuoyu
 * @Date 2023/11/7 22:18
 */


public class Q0092 {
    /**
     * O(n+right-left) O(1)
     */
//    public void change(ListNode p, ListNode s) {
//        if (s == null) return;
//        ListNode tmp = s.next;
//        s.next = p;
//        change(s, tmp);
//    }
//
//    public ListNode reverseBetween(ListNode head, int left, int right) {
//        ListNode rhead = new ListNode(-1, head);
//        ListNode l = rhead;
//        ListNode r = rhead;
//        ListNode h = rhead;
//        ListNode t = rhead;
//
//        while (left-- > 1) {
//            l = l.next;
//        }
//        h = l.next;
//        while (right-- > 0) {
//            t = t.next;
//        }
//        r = t.next;
//        t.next = null;
//
//        change(null, h);
//        l.next = t;
//        h.next = r;
//
//        return rhead.next;
//    }

    /**
     * O(n) O(1)
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) return head;
        ListNode h = new ListNode(-1, head);
        ListNode p = h;
        while (left > 1) {
            p = p.next;
            left--;
            right--;
        }

        ListNode lpre = null;
        ListNode l = p.next;
        ListNode lnext = l.next;
        while (right > 0) {
            l.next = lpre;
            lpre = l;
            l = lnext;
            if (lnext == null) break;
            lnext = lnext.next;
            right--;
        }
        p.next.next = l;
        p.next = lpre;

        return h.next;
    }

    public static void main(String[] args) {
        Q0092 sl = new Q0092();
    }
}